package com.demo.algorithms;

import java.util.Arrays;


public class Sorts {
	public static void swap(int[] nums,int i,int j){
		if(i==j)
			return;
		else{
			nums[i]=nums[i]+nums[j];
			nums[j]=nums[i]-nums[j];
			nums[i]=nums[i]-nums[j];
		}
	}
	public static void bubble(int[] nums){
		for (int i = nums.length-1; i >1; i--) {
			for (int j = 0; j < i; j++) {
				if(nums[j]>nums[j+1]){
					swap(nums,j,j+1);
				}	
			}
		}
	}
	public static void select(int[] nums){
		for (int i = 0; i < nums.length-1; i++) {
			int max=i;
			for (int j = i+1; j < nums.length; j++) {
				if(nums[j]>nums[max]) max=j;
			}
			swap(nums,max,i);
		}
	}
	public static void insert(int[] nums){
		for (int i = 1; i < nums.length; i++) {
			int j=i-1;
			int temp=nums[i];
			while(j>=0&&nums[j]>temp){
				nums[j+1]=nums[j];
				j--;
			}
			nums[j+1]=temp;
		}
	}
	public static int partition(int[] nums,int low,int high){
		int temp=nums[low];
		while(low<high){
			while(nums[high]>=temp&&low<high) high--;
				nums[low]=nums[high];
			while(nums[low]<=temp&&low<high) low++;
				nums[high]=nums[low];
		}
		nums[low]=temp;
		return low;
	}
	public static void quick(int[] nums,int low,int high){
		if(low<high){
			int middle=partition(nums, low, high);
			quick(nums, low, middle-1);
			quick(nums, middle+1, high);
		}
	}
	
	public static void mergesort(int[] nums){
		sort(nums, 0,nums.length-1);
	}
	public static void sort(int[] nums,int low,int high){
		if(low>=high)
			return;
		int center=(low+high)/2;
		sort(nums, low, center);
		sort(nums, center+1, high);
		merge(nums,low,center,high);
	}
	public static void merge(int[] nums,int low ,int center,int high){
		int[] temparray=new int[high-low+1];
		int left2=center+1;
		int start=low;
		int arraytemp=0;
		while(low<=center&&left2<=high){
			if(nums[low]<nums[left2])
				temparray[arraytemp++]=nums[low++];
			else
				temparray[arraytemp++]=nums[left2++];
		}
		while(low<=center){
			temparray[arraytemp++]=nums[low++];
		}
		while(left2<=high){
			temparray[arraytemp++]=nums[left2++];
		}
		arraytemp=0;
		while(start<=high)
			nums[start++]=temparray[arraytemp++];
	}
	public static void heapsort(int[] nums){
		for (int i = 0; i < nums.length; i++) {
			createHeap(nums,nums.length-i-1);
			swap(nums,0,nums.length-i-1);
		}
	}
	public static void createHeap(int[] nums,int lastindex){
		for (int i = (lastindex-1)/2; i>=0; i--) {
			int k=i;
			while(2*k+1<=lastindex){
				int bigindex=2*k+1;
				if(bigindex<lastindex&&nums[bigindex]<nums[bigindex+1]) bigindex++;
				if(nums[k]<nums[bigindex]) {
					swap(nums,k,bigindex);
					k=bigindex;
				}
				else{
					break;
				}
			}
		}
	}
	public static void main(String[] args) {
		int a[]={1,1,6,3,5,2};
//		heapsort(a);
		bubble(a);
		System.out.println(Arrays.toString(a));
	}
	
}

